#include "SortAlgorithms.h"
#include <iostream>
using namespace std;

void MergeSort::Sort(int *inputArray, int start, int end)
{
  int middle;
  if(start < end)
  {
    middle = (end + start )/2;
    
    
    //sort from start to middle
    Sort(inputArray, start, middle);
    
    //sort from middle to end
    Sort(inputArray, middle + 1, end);
    
    //merge the two sorted arrays
    Merge(inputArray, start, middle, end);
	
  }
  return;
}

void MergeSort::Merge(int *inputArray, int start, int middle, int end)
{
  //leftSize is last index - first index + 1
  int leftSize = middle - start + 1;
  
  //right size is last index of array - last index of leftArray
  int rightSize = end - middle;
  
  //allocate memory with size + 1 as size to accomodate for sentinel
  int *leftArray = new int[leftSize + 1];
  int *rightArray = new int[rightSize + 1];
  
  //copy the first leftSize elements of the input array into the leftArray
  for(int i = 0; i< leftSize; i++)
  {
    leftArray[i] = inputArray[start + i];
  }
    leftArray[leftSize] = 99999999;
  
    //this might be confusing at first since it's different 
    //from the book. middle is the index of the last element from leftArray
    //so we really need to start at middle + 1 for first iteration of 
    //filling the right array, hence middle + j + 1
  for(int j = 0; j< rightSize; j++)
  {
    rightArray[j] = inputArray[middle + j + 1];
  }

  //put the sentinel at the position of the last element of 
  //rightArray. that is at index rightSize.
  //Note that rightArray was initialized with size rightSize + 1
  //to accomodate for this
  rightArray[rightSize] = 99999999;
  
  //set i to 0 and j to 0 
  //i is responsible for iterating through leftArray
  //j is responsible for iterating through rightArray
  int i = 0;
  int j = 0;
  
  //end is the last index from inputArray
  //so we are going up to end + 1 exclusive(not inclusive)
  for (int k = start; k < end + 1; k++)
  {
    //if the element from the left array was
    //less than the element from the right array 
    //pick the left array
    if(leftArray[i] < rightArray[j])
    {
      //if an element from the left array was picked
      //bump i
      inputArray[k] = leftArray[i];
      i++;
    }
    else
    {
      //if an element from the rightArray was picked
      //bump j
      inputArray[k] = rightArray[j];
      j++;
    }
  }
  
  //free memory
  delete []leftArray;
  delete []rightArray;
  return;
}